Digital halftoning for the purpose of generating color images with multiple levels has been practical since the mid 1960's (see, for example, "Picture Generation with a Standard Line Printer" by Perry and Mendelsohn, Comm. of the ACM, Vol. 7, No. 5, pp. 311-313). The two major techniques that are in current use are dithering and error diffusion See Digital Halftoning by Ulichney, MIT Press., Cambridge, Mass., pages 77-79, 127, 239-240. The prime dithering techniques are random dither, clustered-dot dither, and dispersed-dot dither. Random dither was developed first but it is rarely used because it produces the poorest quality image.
The other two dither techniques are used with clustered-dot being by far the most prevalent. They are both based on a threshold screen pattern that is generally a fixed size, e.g. 8.times.8 image pixels, which is compared with the input digital image values. If the input digital value is greater than the screen pattern number, the output is set `on`, i.e. 255 for an 8 bit input image, and if it is less, the output is set to 0. The difference between the two techniques is that the lower threshold values are centered in the clustered-dot screen pattern whereas they are scattered in the dispersed-dot screen pattern. As such the clustered-dot technique will have a central dot that increases in size as the signal level increases and the dispersed-dot technique will have small scattered dots that increase in number as the signal level increases. In both techniques the number of levels that can be represented is equal to the size in pixels of the screen pattern, e.g. an 8.times.8 screen can produce 64 unique levels.
Larger patterns mean more levels but also a reduction in the effective resolution because the ability to transition among levels is at a coarser pitch. At the medium pixel rate of copiers and laser printers, e.g. 300-500 dots/inch, the pattern artifacts are visible for screen patterns larger than 4.times.4, and since 16 levels are inadequate precision for typical continuous-tone color imagery a suboptimal resolution/level tradeoff is necessary. This resolution density level tradeoff is illustrated in FIG. 1. A second drawback of dithering is that the pattern for a given level is based on adding an `on` to the pattern of the previous level. This highly constrains the ability to design patterns that have minimal perceived binary noise or modulation at all levels. Efforts to do this for dispersed-dot dither (see "An Optimum Method for Two-Level Rendition of Continuous-Tone Pictures" by B. E. Bayer, Proc. IEEE Int. Conf. Comm. Conference Record, pp. (26-11)-(25-15)) have been severely limited by the requirements for a single screen pattern and a small screen size. Such considerations have led to an increased interest in error diffusion for medium resolution applications.
Error diffusion is fundamentally different from dither in that there is no fixed screen pattern. Instead a recursive algorithm is used that attempts to casually correct errors made by representing the continuous input signal by binary values. The two major components are a matrix of fractions that weight past errors and a threshold operator based on the sum of those weighted errors and the current pixel that determines whether to output an `on` or an `off`. The best error diffusion techniques are two-dimensional, meaning that the error is fed back from previous lines as well as previous pixels. The error feedback mechanism is usually linear in that the sum error is a weighted version of past errors, but the thresholding is highly non-linear making the compound process non-linear. Approximating thresholding as signal-dependent gain, it can be shown that for positive error weights that the output binary signal will be high-pass in uniform regions thus introducing `blue noise` into the image (see Ulichney cited above). This `blue noise` spectrum is shown in FIG. 2. As discussed by Ulichney this `blue noise` is a very favorable feature of error diffusion because the perception of this noise will be reduced by the low-pass filtering of the visual system causing a higher perceived signal-to-noise ratio. Unfortunately the error weights are indirectly related to this preferred noise characteristic and therefore provide suboptimal control, and for certain signal levels the causal feedback can become visually unstable generating correlated patterns or `worms` that are highly objectionable. The most common solution is to randomly modulate the weights which reduces the `worms` but also increases the noise. It is the object of the present invention to provide a new digital halftoning technique that improves the image quality over the aforementioned techniques for all classes of images of interest to a human observer including constant signal levels such as those generated by computer graphics.